package org.apache.commons.graph.collections

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Simple [Disjoint-set](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) implementation.
 *
 * @param <E> the type of elements held in this collection.
</E> */
class DisjointSet<E> {
    /**
     * The map to store the related [DisjointSetNode] for each added element.
     */
    private val disjointSets: MutableMap<E, DisjointSetNode<E>> = HashMap()

    /**
     * Performs the @code{ find} operation by applying the *path compression*.
     *
     * @param node the input DisjointSet node for the @code{ find} operation
     * @return the root node of the path
     */
    private fun find(node: DisjointSetNode<E>): DisjointSetNode<E> {
        if (node == node.parent) {
            return node
        }
        return find(node.parent)
    }

    /**
     * Performs the `find` operation applying the *path compression*.
     *
     * @param e the element has to be find in this `DisjointSet` instance
     * @return the value found
     */
    fun find(e: E): E {
        val node = find(getNode(e))

        if (node == node.parent) {
            return node.element
        }

        node.parent = find(node.parent)

        return node.parent.element
    }

    /**
     * Retrieves the `DisjointSetNode` from the [.disjointSets],
     * if already previously set, creates a new one and push it in [.disjointSets] otherwise.
     *
     * @param e the element which related subset has to be returned
     * @return the input element `DisjointSetNode`
     */
    private fun getNode(e: E): DisjointSetNode<E> {
        var node = disjointSets[e]

        if (node == null) {
            node = DisjointSetNode(e)
            disjointSets[e] = node
        }

        return node
    }

    /**
     * Join two subsets into a single subset, performing the merge by applying the *union by rank*.
     *
     * @param e1 the first element which related subset has to be merged
     * @param e2 the second element which related subset has to be merged
     */
    fun union(e1: E, e2: E) {
        val e1Root = find(getNode(e1))
        val e2Root = find(getNode(e2))

        if (e1Root == e2Root) {
            return
        }

        val comparison = e1Root.compareTo(e2Root)
        if (comparison < 0) {
            e1Root.setParent(e2Root)
        } else if (comparison > 0) {
            e2Root.setParent(e1Root)
        } else {
            e2Root.setParent(e1Root)
            e1Root.increaseRank()
        }
    }
}
